/*
 ------------------------------------------------------------------------------
 Copyright (C) 2006-2007 Team Blur.

 This file is part of the Quantum Engine source code.

 The Quantum Engine source code is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or (at your
 option) any later version.

 The Quantum Engine source code is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 more details.

 You should have received a copy of the GNU General Public License along with
 the Quantum Engine source code; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 ------------------------------------------------------------------------------
*/


#include "cm_local.h"


/*
 ==============================================================================

 LEAF FUNCTIONS

 ==============================================================================
*/


/*
 ==================
 CM_PointInLeaf
 ==================
*/
int CM_PointInLeaf (const odVec3 &point){

	cmNode_t	*node;
	int			side;
	int			num;

	if (!cm.loaded)
		Com_Error(false, "CM_PointInLeaf: map not loaded");

	cm_stats.leafPoints++;	// Optimize counter

	num = 0;

	while (1){
		// If < 0, we are in a leaf node
		if (num < 0)
			break;

		// Find which side of the node we are on
		node = &cm.nodes[num];

		side = node->plane->PointOnSide(point);

		// Go down the appropriate side
		if (side == PLANESIDE_FRONT)
			num = node->children[0];
		else
			num = node->children[1];
	}

	return -1 - num;
}

/*
 ==================
 CM_LeafCluster
 ==================
*/
int CM_LeafCluster (int leafNum){

	if (!cm.loaded)
		Com_Error(false, "CM_LeafCluster: map not loaded");

	if (leafNum < 0 || leafNum >= cm.numLeafs)
		Com_Error(false, "CM_LeafCluster: bad leafNum");

	return cm.leafs[leafNum].cluster;
}

/*
 ==================
 CM_LeafArea
 ==================
*/
int CM_LeafArea (int leafNum){

	if (!cm.loaded)
		Com_Error(false, "CM_LeafArea: map not loaded");

	if (leafNum < 0 || leafNum >= cm.numLeafs)
		Com_Error(false, "CM_LeafArea: bad leafNum");

	return cm.leafs[leafNum].area;
}

/*
 ==================
 CM_LeafCanSeePortalSky
 ==================
*/
bool CM_LeafCanSeePortalSky (int leafNum){

	if (!cm.loaded)
		Com_Error(false, "CM_LeafCanSeePortalSky: map not loaded");

	if (leafNum < 0 || leafNum >= cm.numLeafs)
		Com_Error(false, "CM_LeafCanSeePortalSky: bad leafNum");

	return cm.leafs[leafNum].canSeePortalSky;
}


/*
 ==============================================================================

 PVS

 ==============================================================================
*/


/*
 ==================
 CM_ClusterPVS
 ==================
*/
const byte *CM_ClusterPVS (int clusterNum){

	if (!cm.loaded)
		Com_Error(false, "CM_ClusterPVS: map not loaded");

	if (cm_skipPVS->integerValue || !cm.pvs || clusterNum == -1)
		return cm.noPVS;

	if (clusterNum < 0 || clusterNum >= cm.numClusters)
		Com_Error(false, "CM_ClusterPVS: bad clusterNum");

	return cm.pvs + clusterNum * cm.clusterBytes;
}

/*
 ==================
 CM_RecursivePointInPVS
 ==================
*/
static void CM_RecursivePointInPVS (const odVec3 &point, int num, const byte *pvs, int areaNum, bool *inPVS){

	cmNode_t	*node;
	cmLeaf_t	*leaf;
	int			side;

	while (1){
		// If < 0, we are in a leaf node
		if (num < 0){
			leaf = &cm.leafs[-1 - num];

			if (leaf->cluster == -1 || leaf->area == -1)
				return;

			// Check the PVS
			if (!(pvs[leaf->cluster >> 3] & BIT(leaf->cluster & 7)))
				return;

			// Check area connection
			if (!cm_skipAreas->integerValue){
				if (cm.areas[areaNum].floodNum != cm.areas[leaf->area].floodNum)
					return;
			}

			*inPVS = true;
			break;
		}

		// Find which side of the node we are on
		node = &cm.nodes[num];

		side = node->plane->PointOnSide(point);

		// Go down the appropriate side
		if (side == PLANESIDE_FRONT)
			num = node->children[0];
		else
			num = node->children[1];
	}
}

/*
 ==================
 CM_PointInPVS
 ==================
*/
bool CM_PointInPVS (const odVec3 &point, int clusterNum, int areaNum){

	bool	inPVS = false;

	if (!cm.loaded)
		Com_Error(false, "CM_PointInPVS: map not loaded");

	if (cm_skipPVS->integerValue || !cm.pvs || clusterNum == -1 || areaNum == -1)
		return true;

	if (clusterNum < 0 || clusterNum >= cm.numClusters)
		Com_Error(false, "CM_PointInPVS: bad clusterNum");

	if (areaNum < 0 || areaNum >= cm.numAreas)
		Com_Error(false, "CM_PointInPVS: bad areaNum");

	cm_stats.pvsPoints++;	// Optimize counter

	CM_RecursivePointInPVS(point, 0, cm.pvs + clusterNum * cm.clusterBytes, areaNum, &inPVS);

	return inPVS;
}

/*
 ==================
 CM_RecursiveBoundsInPVS
 ==================
*/
static void CM_RecursiveBoundsInPVS (const odBounds &bounds, int num, const byte *pvs, int areaNum, bool *inPVS){

	cmNode_t	*node;
	cmLeaf_t	*leaf;
	int			side;

	if (*inPVS)
		return;		// Already in PVS

	// If < 0, we are in a leaf node
	if (num < 0){
		leaf = &cm.leafs[-1 - num];

		if (leaf->cluster == -1 || leaf->area == -1)
			return;

		// Check the PVS
		if (!(pvs[leaf->cluster >> 3] & BIT(leaf->cluster & 7)))
			return;

		// Check area connection
		if (!cm_skipAreas->integerValue){
			if (cm.areas[areaNum].floodNum != cm.areas[leaf->area].floodNum)
				return;
		}

		*inPVS = true;
		return;
	}

	// Find which side of the node we are on
	node = &cm.nodes[num];

	side = node->plane->BoundsOnSide(bounds);

	// Go down the appropriate sides
	if (side == PLANESIDE_FRONT){
		CM_RecursiveBoundsInPVS(bounds, node->children[0], pvs, areaNum, inPVS);
		return;
	}
	if (side == PLANESIDE_BACK){
		CM_RecursiveBoundsInPVS(bounds, node->children[1], pvs, areaNum, inPVS);
		return;
	}

	CM_RecursiveBoundsInPVS(bounds, node->children[0], pvs, areaNum, inPVS);
	CM_RecursiveBoundsInPVS(bounds, node->children[1], pvs, areaNum, inPVS);
}

/*
 ==================
 CM_BoundsInPVS
 ==================
*/
bool CM_BoundsInPVS (const odBounds &bounds, int clusterNum, int areaNum){

	bool	inPVS = false;

	if (!cm.loaded)
		Com_Error(false, "CM_BoundsInPVS: map not loaded");

	if (cm_skipPVS->integerValue || !cm.pvs || clusterNum == -1 || areaNum == -1)
		return true;

	if (clusterNum < 0 || clusterNum >= cm.numClusters)
		Com_Error(false, "CM_BoundsInPVS: bad clusterNum");

	if (areaNum < 0 || areaNum >= cm.numAreas)
		Com_Error(false, "CM_BoundsInPVS: bad areaNum");

	cm_stats.pvsBounds++;	// Optimize counter

	CM_RecursiveBoundsInPVS(bounds, 0, cm.pvs + clusterNum * cm.clusterBytes, areaNum, &inPVS);

	return inPVS;
}


/*
 ==============================================================================

 PORTALS & AREAS

 ==============================================================================
*/

typedef struct {
	bool		outside;
	bool		contacted[BSP_MAX_AREAS];

	int *		areas;
	int			numAreas;
	int			maxAreas;
} areaList_t;


/*
 ==================
 CM_RecursiveFloodAreaConnections
 ==================
*/
static void CM_RecursiveFloodAreaConnections (int areaNum, int floodNum){

	cmArea_t	*area;
	cmPortal_t	*portal;
	int			i, num;

	area = &cm.areas[areaNum];

	if (area->floodCount == cm.floodCount){
		if (area->floodNum == floodNum)
			return;

		Com_Error(false, "CM_RecursiveFloodAreaConnections: reflooded");
	}

	area->floodNum = floodNum;
	area->floodCount = cm.floodCount;

	for (i = 0; i < area->numAreaPortals; i++){
		num = cm.areaPortals[area->firstAreaPortal + i];
		portal = &cm.portals[num];

		if (!portal->open)
			continue;

		if (portal->areas[0] == areaNum)
			CM_RecursiveFloodAreaConnections(portal->areas[1], floodNum);
		else if (portal->areas[1] == areaNum)
			CM_RecursiveFloodAreaConnections(portal->areas[0], floodNum);
	}
}

/*
 ==================
 CM_FloodAreaConnections
 ==================
*/
void CM_FloodAreaConnections (void){

	cmArea_t	*area;
	int			floodNum;
	int			i;

	// All current floods are now invalid
	floodNum = 0;
	cm.floodCount++;

	for (i = 0, area = cm.areas; i < cm.numAreas; i++, area++){
		if (area->floodCount == cm.floodCount)
			continue;		// Already flooded into

		floodNum++;
		CM_RecursiveFloodAreaConnections(i, floodNum);
	}
}

/*
 ==================
 CM_NumPortals
 ==================
*/
int CM_NumPortals (void){

	if (!cm.loaded)
		Com_Error(false, "CM_NumPortals: map not loaded");

	return cm.numPortals;
}

/*
 ==================
 CM_FindPortal
 ==================
*/
int CM_FindPortal (const odBounds &bounds){

	cmPortal_t		*portal;
	cmBrush_t		*brush;
	cmBrushSide_t	*side;
	odPlane			*plane;
	int				i, j;

	if (!cm.loaded)
		Com_Error(false, "CM_FindPortal: map not loaded");

	// Check for intersection with a portal
	for (i = 0, portal = cm.portals; i < cm.numPortals; i++, portal++){
		// Check the area portal brush
		brush = &cm.brushes[portal->portalNum];

		for (j = 0; j < brush->numSides; j++){
			side = &brush->sides[j];
			plane = side->plane;

			// If completely in front of face, no intersection
			if (plane->BoundsOnSide(bounds) == PLANESIDE_FRONT)
				break;
		}

		// If the brush was intersected, return this portal
		if (j == brush->numSides)
			return i;
	}

	return -1;
}

/*
 ==================
 CM_SetPortalState
 ==================
*/
void CM_SetPortalState (int portalNum, bool open){

	if (!cm.loaded)
		Com_Error(false, "CM_SetPortalState: map not loaded");

	if (portalNum == -1)
		return;

	if (portalNum < 0 || portalNum >= cm.numPortals)
		Com_Error(false, "CM_SetPortalState: bad portalNum");

	if (cm.portals[portalNum].open == open)
		return;
	cm.portals[portalNum].open = open;

	CM_FloodAreaConnections();
}

/*
 ==================
 CM_GetPortalState
 ==================
*/
bool CM_GetPortalState (int portalNum){

	if (!cm.loaded)
		Com_Error(false, "CM_GetPortalState: map not loaded");

	if (portalNum == -1)
		return false;

	if (portalNum < 0 || portalNum >= cm.numPortals)
		Com_Error(false, "CM_GetPortalState: bad portalNum");

	return cm.portals[portalNum].open;
}

/*
 ==================
 CM_WritePortalBits
 ==================
*/
int CM_WritePortalBits (byte *buffer){

	cmPortal_t	*portal;
	int			bytes;
	int			i;

	if (!cm.loaded)
		Com_Error(false, "CM_WritePortalBits: map not loaded");

	bytes = (cm.numPortals + 7) >> 3;

	memset(buffer, 0, bytes);

	for (i = 0, portal = cm.portals; i < cm.numPortals; i++, portal++){
		if (!portal->open)
			continue;

		buffer[i >> 3] |= BIT(i & 7);
	}

	return bytes;
}

/*
 ==================
 CM_AreasAreConnected
 ==================
*/
bool CM_AreasAreConnected (int areaNum1, int areaNum2){

	if (!cm.loaded)
		Com_Error(false, "CM_AreasAreConnected: map not loaded");

	if (cm_skipAreas->integerValue)
		return true;

	if (areaNum1 == -1 || areaNum2 == -1)
		return false;

	if ((areaNum1 < 0 || areaNum1 >= cm.numAreas) || (areaNum2 < 0 || areaNum2 >= cm.numAreas))
		Com_Error(false, "CM_AreasAreConnected: bad areaNum");

	if (cm.areas[areaNum1].floodNum != cm.areas[areaNum2].floodNum)
		return false;

	return true;
}

/*
 ==================
 CM_NumAreas
 ==================
*/
int CM_NumAreas (void){

	if (!cm.loaded)
		Com_Error(false, "CM_NumAreas: map not loaded");

	return cm.numAreas;
}

/*
 ==================
 CM_PointInArea
 ==================
*/
int CM_PointInArea (const odVec3 &point){

	cmNode_t	*node;
	cmLeaf_t	*leaf;
	int			side;
	int			num;

	if (!cm.loaded)
		Com_Error(false, "CM_PointInArea: map not loaded");

	cm_stats.areaPoints++;	// Optimize counter

	num = 0;

	while (1){
		// If < 0, we are in a leaf node
		if (num < 0){
			leaf = &cm.leafs[-1 - num];
			break;
		}

		// Find which side of the node we are on
		node = &cm.nodes[num];

		side = node->plane->PointOnSide(point);

		// Go down the appropriate side
		if (side == PLANESIDE_FRONT)
			num = node->children[0];
		else
			num = node->children[1];
	}

	return leaf->area;
}

/*
 ==================
 CM_RecursiveBoundsInAreas
 ==================
*/
static void CM_RecursiveBoundsInAreas (const odBounds &bounds, int num, areaList_t *areaList){

	cmNode_t	*node;
	cmLeaf_t	*leaf;
	int			side;

	if (areaList->numAreas == areaList->maxAreas)
		return;		// Can't hold any more

	// If < 0, we are in a leaf node
	if (num < 0){
		leaf = &cm.leafs[-1 - num];

		if (leaf->area == -1){
			if (areaList->outside)
				return;		// Already added this area from another leaf
			areaList->outside = true;
		}
		else {
			if (areaList->contacted[leaf->area])
				return;		// Already added this area from another leaf
			areaList->contacted[leaf->area] = true;
		}

		// Add the area
		areaList->areas[areaList->numAreas++] = leaf->area;
		return;
	}

	// Find which side of the node we are on
	node = &cm.nodes[num];

	side = node->plane->BoundsOnSide(bounds);

	// Go down the appropriate sides
	if (side == PLANESIDE_FRONT){
		CM_RecursiveBoundsInAreas(bounds, node->children[0], areaList);
		return;
	}
	if (side == PLANESIDE_BACK){
		CM_RecursiveBoundsInAreas(bounds, node->children[1], areaList);
		return;
	}

	CM_RecursiveBoundsInAreas(bounds, node->children[0], areaList);
	CM_RecursiveBoundsInAreas(bounds, node->children[1], areaList);
}

/*
 ==================
 CM_BoundsInAreas
 ==================
*/
int CM_BoundsInAreas (const odBounds &bounds, int *areas, int maxAreas){

	areaList_t	areaList;

	if (!cm.loaded)
		Com_Error(false, "CM_BoundsInAreas: map not loaded");

	cm_stats.areaBounds++;	// Optimize counter

	memset(&areaList, 0, sizeof(areaList_t));

	areaList.areas = areas;
	areaList.numAreas = 0;
	areaList.maxAreas = maxAreas;

	CM_RecursiveBoundsInAreas(bounds, 0, &areaList);

	return areaList.numAreas;
}

/*
 ==================
 CM_NumPortalsInArea
 ==================
*/
int CM_NumPortalsInArea (int areaNum){

	if (!cm.loaded)
		Com_Error(false, "CM_NumPortalsInArea: map not loaded");

	if (areaNum == -1)
		return 0;

	if (areaNum < 0 || areaNum >= cm.numAreas)
		Com_Error(false, "CM_NumPortalsInArea: bad areaNum");

	return cm.areas[areaNum].numAreaPortals;
}

/*
 ==================
 CM_GetPortalFromArea
 ==================
*/
void CM_GetPortalFromArea (int areaNum, int portalNum, areaPortal_t *areaPortal){

	cmArea_t	*area;
	cmPortal_t	*portal;
	int			num;

	if (!cm.loaded)
		Com_Error(false, "CM_GetPortalFromArea: map not loaded");

	if (areaNum == -1 || portalNum == -1){
		areaPortal->areas[0] = -1;
		areaPortal->areas[1] = -1;
		areaPortal->open = false;

		return;
	}

	if (areaNum < 0 || areaNum >= cm.numAreas)
		Com_Error(false, "CM_GetPortalFromArea: bad areaNum");

	area = &cm.areas[areaNum];

	if (portalNum < 0 || portalNum >= area->numAreaPortals)
		Com_Error(false, "CM_GetPortalFromArea: bad portalNum");

	num = cm.areaPortals[area->firstAreaPortal + portalNum];
	portal = &cm.portals[num];

	areaPortal->areas[0] = portal->areas[0];
	areaPortal->areas[1] = portal->areas[1];
	areaPortal->open = portal->open;
}

/*
 ==================
 CM_WriteAreaBits
 ==================
*/
int CM_WriteAreaBits (int areaNum, byte *buffer){

	cmArea_t	*area;
	int			bytes, floodNum;
	int			i;

	if (!cm.loaded)
		Com_Error(false, "CM_WriteAreaBits: map not loaded");

	bytes = (cm.numAreas + 7) >> 3;

	if (cm_skipAreas->integerValue || areaNum == -1){
		memset(buffer, 0xFF, bytes);
		return bytes;
	}

	if (areaNum < 0 || areaNum >= cm.numAreas)
		Com_Error(false, "CM_WriteAreaBits: bad areaNum");

	memset(buffer, 0, bytes);

	floodNum = cm.areas[areaNum].floodNum;

	for (i = 0, area = cm.areas; i < cm.numAreas; i++, area++){
		if (area->floodNum != floodNum)
			continue;

		buffer[i >> 3] |= BIT(i & 7);
	}

	return bytes;
}
